The invention relates to a method for joining a cluster of communicating electronic devices, said method being implemented by a processing unit of one of said electronic devices communicating with peers through a wireless communication network.
The invention further relates to a system including a plurality of communicating electronic devices implementing such a joining method.
As a non-limiting example preferred application, the invention is described through an example application relative to the collection of physical properties, for example a temperature, moisture level, brightness, vibration frequency, shocks, etc., related to the internal and/or external environments of containers of goods or merchandise, or more generally, containers. According to the example application, said containers are grouped together and/or stacked in a storage area or traveling on a transport platform such as a container ship, a freight train or any other appropriate transportation platform. Each container cooperates with one of said communicating electronic devices. The latter are responsible for collecting and conveying said properties through service messages to peer devices acting as “cluster heads” or “heads.” One of the missions of a communicating electronic device acting as a cluster head, which we will call “Head” in the rest of the document, consists of carrying out a predetermined service. Such a service may for example consist of aggregating data collected by the communicating devices and sending said data, after it has been aggregated, to a remote entity, through a long-range or long-distance connection of the satellite connection or radio telephony connection type. The invention cannot, however, be limited solely to this example application. More generally, a Head is responsible for carrying out a given service related to data collected and conveyed by its peers, said given service being able to relate to supervision or alarm management, in place of or in addition to communication with a remote entity.
Numerous typologies or configurations of networks of communicating objects exist. FIG. 1 schematically shows two examples of wireless communication networks. Irrespective of the operated network, each communicating electronic device, which will also generally be called “node” of said network, implements a communication method allowing it to exchange data messages and/or service messages with a third-party or peer node. Thus, the network N1 situates forty communicating electronic devices respectively referenced a1 to a8, b1 to b8, c1 to c8, d1 to d8 and e1 to e8 in FIG. 1.
Such a network is generally described as a multi-hop network. According to this typology, a first node, which we will call “source,” develops a service message, represented in FIG. 1 by double arrow, comprising data related, non-limitingly, to a property measured by a sensor cooperating with said first node, intended for a second “recipient” node.
Unlike a necessarily direct communication between two nodes of a single-hop network, the communication between first and second nodes may be direct or indirect between two nodes of a multi-hop network such as the network N1 according to FIG. 1. Thus, according to an indirect communication, a message sent from a source node can be relayed by one or several third-party or intermediate nodes, the respective roles of which consist of relaying said message from the source node so that said message is in fine conveyed to and received by the recipient node. Such nodes make up clusters. As an example, a cluster C11 is shown by a circle in dotted lines in FIG. 1. The path followed by a service message originating from a source node and intended for a receiving node, via one or several relay nodes, is generally called “route.” Thus, according to FIG. 1, a message sent from the node a4 to the node d2 will successively be relayed by the relay nodes b4 and c3.
The communication within multi-hop communication networks is generally done by radio. Such communication is generally short-range, i.e., several meters to several tens of meters, such that service messages are transmitted from one to another between the different nodes. When data is supposed to be conveyed to a server, or more generally a remote entity, a second communication mode is implemented, for example, by GSM (Global System for Mobile Communication) or GPRS (General Packet Radio Service), or by satellite connection.
As indicated as a preferred example by FIG. 2, a node generally and primarily consists of a communicating electronic device 10 including a processing unit 11, for example in the form of a microcontroller, cooperating with a data memory 12, optionally a program memory 14, said memories optionally being separated. The processing unit 11 cooperates with said memories 12 and 14 using internal communication buses, shown in FIG. 2 by double arrows with a simple line. Generally, a communicating electronic device 10 includes one or several measuring sensors 15 for measuring a physical property related to the environment of said device 10. Such a sensor can measure the surrounding temperature, a moisture level or the presence and/or absence of light. The device 10 further includes first communication means 13 cooperating with the processing unit 11 and providing wireless nearby communication with any other communicating electronic device 10i situated within communication range. It may also include second communication means 16 of the “long-distance” type also cooperating with the processing unit 11. These second communication means allow such a device 10 the ability to send a remote entity, for example a server RS, data through messages MC distributed by a network RR for example using the GSM, GPRS or satellite technologies. To operate, i.e., in order for the processing unit 11 to carry out a method derived from the interpretation or performance, by said processing unit, of program instructions P saved in the program memory 14, the device 10 includes an electricity source 17, in the form of one or several batteries, for example. A node's capacity to communicate, or quite simply to be able to operate, is directly related to the remaining and available energy capacity of said node. Indeed, the exchanges between nodes, the processing operations or calculations implemented by the latter use exchanged data, as well as the possible and remote conveyance of data collected within a network or a cluster of communicating electronic devices, are all electricity-consuming actions.
Some builders or operators have tried to optimize networks or communication methods, implemented by nodes within a network or a cluster, to globally preserve the electricity capacity of the network or the cluster. Globally, a first approach consists of distributing the energy cost resulting from exchanges between the nodes over all of said nodes of the network or the cluster. A second approach consists of distributing the energy consumption resulting from the processing operations implemented on collected data, for example a long-distance transmission, over most of the nodes, thus pooling the electricity consumption over a plurality of nodes. Thus, whether the contactless communication network is in the single-hop or multi-hop configuration, a node may arbitrarily be designated or promoted as “Head,” or at the very least as cluster head, or Head node. In connection with FIG. 1, a device acting as Head is shown by a circle drawn in thick lines. This is node d2 for network N1. The node d2 thus acts as Head of the clusters C11. In this way, the consumed energy, in particular for the remote transmission of data collected within a network, is pooled over a plurality of nodes. Alternatively, the heads can be designated randomly, or more specifically can designate themselves as heads randomly, as long as the latter have sufficient hardware and/or software resources to carry out a predetermined service.
As an example, the “LEACH” method, as in particular described by the document titled “An Application-Specific Protocol Architecture for Wireless Microsensor Networks” (W. Heinzelman, A. Chandrakasan, H. Balakrishnan—IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 1, NO. 4, OCTOBER 2002), makes it possible, in a single-hop network, to randomly designate a node for it to become Head. The other nodes belonging to the cluster of said Head, nodes that we will respectively call “Member,” send the cluster Head, therefore the Head, their service messages. In connection with FIG. 1, each Member node is shown by a circle drawn in thin lines. Thus, within the network N1, the Head d2 communicates directly with the nodes c1 to c4, d1, d3 and d4, as well as with the nodes e1 to e4. Via the Member c1, the Head d2 communicates with the Member b1, which in turn can relay messages to or from the Member a1. The Head d2 collects said data sent from different Member nodes, processes it, aggregates it or consolidates it, and for example initiates a long-range transmission to a remote entity, such as a server RS described in connection with FIG. 2. According to the known technique, once a node has acted as Head, it cannot assume this role again before a predetermined length of time has passed. A new Member node is then randomly designated Head, thus ensuring a continuity of service. In order for a node, which we will call “loose,” represented by a circle shown in double lines in connection with FIG. 1, to be able to “join” a Head and thus form a cluster or join an existing cluster, such a loose node, situated within radio range of a promoted node or node designated as Head, is arranged to receive an enrollment message MH coming from said Head, generally issued in the form of an undifferentiated transmission (also called “broadcast”) of enrollment messages MH intended for any node situated within radio range of the Head. FIG. 1 makes it possible, through the network N1, to describe the resultant of a transmission of a message MH sent from the node d2, designated to act as Head, this message MH being sent according to a short-range broadcast mode to the nodes situated within communication range. Upon receiving such an enrollment message MH, a loose node, for example the node e2, updates its data memory, said memory cooperating with the processing unit to record the coordinates or the value of the identifier of the Head therein, or the identifier of the node d2 in connection with FIG. 1. The device e2, previously loose, becomes a Member of the cluster C11. It thus appears shown by a circle in thin lines in FIG. 1. The device d2, acting as Head, becomes the recipient of any service message MS including data collected by the device e2 newly having become a Member of the cluster C11 like the other Member devices of said cluster. The transmission of the message MH by the node d2 has a limited range. Consequently, nodes situated outside the range do not receive the message MH as an intelligible message, or do not receive it all. The nodes that are outside the range of d2, such as the nodes a5 to a8, or the nodes b5 to b8, remain loose nodes, shown by circles drawn in double lines. The cluster C11 only includes the node d2, acting as Head, and the Member nodes, i.e., having accepted the enrollment of the Head d2.
Transposing the LEACH teaching to the context of a multi-hop network, like the network N1 described in connection with FIG. 1, could lead one to believe that the nodes, becoming Members of a cluster including a node acting as Head, record, within their respective data memories, the route, i.e., the value of the identifier of the node acting as Head and at least the value of the identifier of the node having relayed the enrollment message of said Head, or alternatively, the respective values of the identifiers of the intermediate or relay nodes separating it from said Head. Thus, as an example, the node c2 saves the value of the identifier of the Head d2, having directly received an enrollment message MH from said node d2. The node b2 in turn also records the value of the identifier of the node d2, the value of that of the node c2 having relayed the enrollment message MH of d2 in favor of the node b2.
In theory, or at least according to a perfect application mode, such an approach makes it possible to preserve the overall energy resources of a communication network including a plurality of communicating nodes. In practice or in reality, and in particular according to application or operating domains of such a communication network in connection with the transport of containers cooperating with communicating electronic devices, such a solution remains irrelevant, or at least ineffective.
Indeed, let us consider the example of the preferred and non-limiting example consisting of the use of a wireless communication network whose nodes record, collect and send measurements related to a plurality of containers, such as containers of goods or merchandise. Imagine that each container is associated with a communicating electronic device implementing a communication method such as LEACH or an equivalent of the multi-hop type. According to this hypothesis, each communicating electronic device associated with a container acts as node within the wireless network, like the network N1 described in connection with FIG. 1. Let us imagine that the communication mode between nodes is done by radio channel. Aside from the fact that a communication method of the LEACH type requires a single-hop approach, thus requiring each node to be able to communicate directly with a Head, the relative arrangement of the containers, for example on a ship, in a storage area or on any road or rail transport platform, creates an application context, such that a node designated as Head may not or may no longer be able to perform its mission, for example consisting of sending aggregated data to a remote unit, due solely to its positioning in a stack of containers, for instance. Indeed, there are many obstacles formed by a transport platform and/or a storage area, due to the partitioning or partial confinement imposed by the structure receiving the containers, or by the interactions mutually created by the containers themselves, the stacking of which may cause a deterioration, or even loss of the ability for a Head to perform a long-range transmission. The risk of data loss, slow data conveyance, as well as needless and irrelevant energy expenses to “animate” a cluster whose Head would not be able to effectively perform its role or service, is high. This risk is even higher in the case where random elections of consecutive heads results in fruitless “choices.” To resolve such drawbacks, the applicants have designed a wireless communication network that is particularly innovative and high-performing, irrespective of the relative arrangement of the nodes and irrespective of the application or operating framework of said network, whether it is of the single-hop or multi-hop type. Such a network makes it possible to optimize the overall capacity of the network to perform a predetermined service from data collected by the different nodes. It is primarily based on a method of joining a cluster of communicating devices according to the capacity of a Head to assume such a role, for example and non-limitingly to send data according to a long-distance communication mode. Each node implementing such a method may decide to act as Head if it is capable of doing so. Furthermore, any loose node may decide whether to join a cluster based on the capacity of the Head, advantageously self-designated. Additionally, the applicants have designed a wireless communication network, particularly innovative and robust, including when nodes making up said network are mobile relative to one another or when the topology of said network proves to be particularly fluctuating. According to this innovation, any loose node may request, on demand, an affiliation procedure with a Member of a cluster. Such an affiliation procedure may follow from an adaptation of a network like that previously described and illustrated in connection with FIG. 1. An affiliation request of a loose node is shown by an arrow in double lines. In the case at hand, it involves the loose node a4, previously loose, which is requesting an affiliation with the node b4, Member of the cluster C11 whose Head is the node d2. The node a4 becomes Affiliated with the cluster C11, shown by a broken circle. Thus, while a4 was not situated to receive an enrollment message MH from the Head d2, it can, at its request, join the cluster C11. Each node, implementing such an affiliation procedure, can more generally, at its request and independently of the enrollment policy of a Head, requested affiliation from a Member of a cluster, and thus send service messages to said Head, in particular via the Member node having accepted the affiliation procedure. It is thus possible to extend clusters formed after an enrollment procedure, or even to transform a single-hop network into a “pseudo-multi-hop network,” or more specifically to adapt a single-hop network whereof a cluster becomes a multi-hop-type structure, a Member node, having accepted an affiliation request, working as a relay node of the affiliated node to send service messages.
Irrespective of the type of network operated, the respective capacities of the nodes implementing a joining and/or affiliation method with a cluster evolve over time.
Although it proposes a significant advance, such a solution, like the aforementioned concurrent solutions, has certain limitations or drawbacks, in particular if such a communication network is used in an application context for which the topology of said network is particularly prone to change. Indeed, irrespective of the selected communication network, the routes or topologies, i.e., the formation or destruction of clusters, of said network are not updated regularly enough or often enough to account for the dynamics of said network. Using known solutions, if such updates were done at a high frequency, the number of enrollment, cluster destruction or service messages would increase tenfold, such that the main objective of preserving energy consumption of the nodes of the network would not be met.
Furthermore, the establishment of a very deep cluster, i.e., according to which a Member can be located at a substantial difference in number of hops, can generate significant message traffic inherent, for example, to the enrollment MH or service MS message relayed by the relay Members. Such relays iterated at a high frequency, which is also by numerous Members, can compromise the energy capacities of said relay Members to collect data, produce and transmit their own service messages to a Head. For a single-hop network, the depth is set at one hop. For a multi-hop network, there is no known method making it possible to wisely limit, or even dynamically regulate, the depth of a cluster homogenously and in a controlled manner.